package 剑指offer;

import java.util.LinkedList;
import java.util.Queue;

public class _37序列化二叉树 {
	public static void main(String[] args) {
		String data = "[1,2,3,null,null,4,5,null,null,null,null]";
		TreeNode treeNode = deserialize(data);
		System.out.println(treeNode);
		System.out.println(serialize(treeNode));
		System.out.println(deserialize(serialize(treeNode)));
	}
	/**
	 * 
	 *@time 2021年3月4日下午4:09:26
	 * 
	 *@param root
	 *@return String
	 *
	 *@see BFS 广度优先搜索
	 */
    public static String serialize(TreeNode root) {
    	if(root == null) return "[]";
    	StringBuilder sb = new StringBuilder("[");
    	Queue<TreeNode> queue = new LinkedList<>();
    	queue.add(root);
    	System.out.println(root);
    	while(!queue.isEmpty()) {
    		TreeNode node = queue.poll();
    		if(node !=null) {
    			sb.append(node.val+",");
    			queue.add(node.left);
    			queue.add(node.right);
    		}
    		else sb.append("null,");
    	}
    	sb.deleteCharAt(sb.length()-1);
    	sb.append("]");
		return sb.toString();
        
    }

    
    public static TreeNode deserialize(String data) {
    	if(data.equals("[]")) return null;
    	String []str = data.substring(1, data.length() - 1).split(",");
		TreeNode root = new TreeNode(Integer.parseInt(str[0])); 
		 Queue<TreeNode> queue = new LinkedList<>();
		 queue.add(root);
		 int index=1;
		 while(!queue.isEmpty()) {
			 TreeNode node = queue.poll();
			 if(!str[index].equals("null")) {
				 node.left = new TreeNode(Integer.parseInt(str[index])); 
				 queue.add(node.left);
			 }
			 index++;
			if(!str[index].equals("null")) {
				node.right = new TreeNode(Integer.parseInt(str[index])); 
				queue.add(node.right);
			}
			index++;
		 }
    	return root;
        
    }
    
}
